package leetcode;
//寻找两个有序数组中位数
public class FindMedianSortedArrays {
    public static void main(String[] args) {
        int[] nums1 = new int[]{1,2};
        int[] nums2 = new int[]{3,4};
        double arrays = findMedianSortedArrays(nums1, nums2);
        System.out.println(arrays);
    }
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length){
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }
        int m =nums1.length;
        int n = nums2.length;
        int totalLeft = (m + n +1)/2;
        int left = 0;
        int right = m;

        //nums1[i] > nums2[j] && nums1[i-1]<num2[j+1];
        while (left < right){
            int i = (left + right + 1) / 2;
            int j = totalLeft - i;
            if (nums1[i-1] > nums2[j]){
                right = i -1; //搜索区间 [left,i-1]
            }else {
                left = i; //搜索区间[i,right]
            }
        }
        //循环结束，二分查找完毕
        int i = left;
        int j = totalLeft - i;
        int nums1LeftMax = i == 0 ? Integer.MIN_VALUE:nums1[i-1];
        int nums1RightMin = i == m ? Integer.MAX_VALUE:nums1[i];
        int nums2LeftMax = j == 0 ? Integer.MIN_VALUE:nums2[j-1];
        int nums2RightMin = j == n ? Integer.MAX_VALUE:nums2[j];

        if ((m + n) % 2 ==1){//奇数
            return Math.max(nums1LeftMax,nums2LeftMax);
        }else {//偶数
            return (double)(Math.max(nums1LeftMax,nums2LeftMax) + Math.min(nums1RightMin,nums2RightMin))/2;
        }
    }
}
